W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Consider an expression , containing integer constants from 0 to 9, variables from to , and the following operations: addition, multiplication and exponentiation with a constant exponent. Quite surprisingly, each of the variables appears in the expression at most once. For a given prime number , we would like to know how many roots modulo the polynomial represented by this expression has. In other words, we want to count the number of ways in which integers from to can be assigned to the variables in , so that the value of is divisible by . Since the number of such roots can turn out large, it suffices to output it modulo .
For example, the polynomial represented by the following expression:
has 15 roots modulo , among which the roots:
can be found.
More formally, an expression is defined as follows:
The first line of input contains one prime number (). The second line contains an expression as specified above, described by a sequence of at most 300 characters 0, 1, ..., 9, a, b, ..., z, +, *, ^, (, ), without any white space.
Let denote the number of roots modulo of the polynomial . Your program should output one non-negative integer, .
For the input data:
3 (((a+y)*(z+8))^2)
the correct result is:
15
Task author: Jakub Radoszewski.